Thực đơn
Giải thuật Euclid Ví dụTính ước số chung lớn nhất của 91 và 287.
Trước hết lấy 287 (số lớn hơn trong 2 số) chia cho 91:
287 = 91*3 + 14 (91 & 14 sẽ được dùng cho vòng lặp kế)Nhận xét: bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi 287 - 91*3 = 14. Tương tự, số chia hết bởi 91 và 14 cũng chia hết bởi 91*3 + 14 = 287. Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán trở thành tìm ƯSCLN(91,14). Lặp lại quy trình trên cho đến khi phép chia không còn số dư như sau:
91 = 14*6 + 7 (14 & 7 sẽ được dùng cho vòng lặp kế)14 = 7*2 (không còn số dư, kết thúc, nhận 7 làm kết quả)Cuối cùng ta có: 7 = ƯSCLN(7,0) = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).
Thực đơn
Giải thuật Euclid Ví dụLiên quan
Giải Giải vô địch bóng đá châu Âu 2012 Giải bóng đá Ngoại hạng Anh Giải vô địch bóng đá thế giới Giải vô địch bóng đá thế giới 2022 Giải vô địch bóng đá châu Âu 2020 Giải vô địch bóng đá châu Âu 2024 Giải vô địch bóng đá châu Âu 2016 Giải bóng đá Vô địch Quốc gia Việt Nam Giải vô địch bóng đá thế giới 2018Tài liệu tham khảo
WikiPedia: Giải thuật Euclid https://commons.wikimedia.org/wiki/Category:Euclid...